class HashTableSearch:
    """
    散列表搜索类，包含了散列表搜索算法的实现。
    """

    def linear_search(self, hashtable, key):
        """
        在散列表中执行线性搜索以找到目标元素。

        概念：
        - 线性搜索通过遍历散列表中的每个键值对并将其与目标键进行比较来进行搜索。

        属性：
        - 时间复杂度取决于散列表的大小和冲突的数量。

        参数：
            hashtable (dict)：待搜索的散列表。
            key：要搜索的目标键。

        返回值：
            object：如果找到目标键，则返回对应的值；如果未找到目标键，则返回None。
        """
        for k, v in hashtable.items():
            if k == key:
                return v
        return None

    def hash_search(self, hashtable, key):
        """
        在散列表中执行散列搜索以找到目标元素。

        概念：
        - 散列搜索通过散列函数将目标键转换为散列值，并使用散列值在散列表中查找对应的值。

        属性：
        - 时间复杂度取决于散列表的大小和冲突的数量。

        参数：
            hashtable (dict)：待搜索的散列表。
            key：要搜索的目标键。

        返回值：
            object：如果找到目标键，则返回对应的值；如果未找到目标键，则返回None。
        """
        hashed_key = hash(key) % len(hashtable)

        if hashed_key in hashtable:
            return hashtable[hashed_key]
        return None

    def linear_probing_search(self, hashtable, key):
        """
        在散列表中执行线性探测以解决冲突，并找到目标元素。

        概念：
        - 线性探测通过在发生冲突的位置进行线性探测来找到下一个可用的位置。
        - 如果目标键的位置已经被占用，则向后线性探测直到找到空槽或目标键。

        属性：
        - 时间复杂度取决于散列表的大小和冲突的数量。

        参数：
            hashtable (dict)：待搜索的散列表。
            key：要搜索的目标键。

        返回值：
            object：如果找到目标键，则返回对应的值；如果未找到目标键，则返回None。
        """
        hashed_key = hash(key) % len(hashtable)

        while hashed_key in hashtable:
            if hashtable[hashed_key][0] == key:
                return hashtable[hashed_key][1]
            hashed_key = (hashed_key + 1) % len(hashtable)

        return None

    def quadratic_probing_search(self, hashtable, key):
        """
        在散列表中执行二次探测以解决冲突，并找到目标元素。

        概念：
        - 二次探测通过在发生冲突的位置进行二次探测来找到下一个可用的位置。
        - 如果目标键的位置已经被占用，则根据二次方程计算下一个探测位置。

        属性：
        - 时间复杂度取决于散列表的大小和冲突的数量。

        参数：
            hashtable (dict)：待搜索的散列表。
            key：要搜索的目标键。

        返回值：
            object：如果找到目标键，则返回对应的值；如果未找到目标键，则返回None。
        """
        hashed_key = hash(key) % len(hashtable)
        collisions = 0

        while hashed_key in hashtable:
            if hashtable[hashed_key][0] == key:
                return hashtable[hashed_key][1]

            collisions += 1
            hashed_key = (hashed_key + collisions**2) % len(hashtable)

        return None

    def double_hashing_search(self, hashtable, key):
        """
        在散列表中执行双重散列以解决冲突，并找到目标元素。

        概念：
        - 双重散列通过使用第二个散列函数来计算探测步长，并在发生冲突的位置进行双重散列探测。
        - 如果目标键的位置已经被占用，则根据第二个散列函数计算下一个探测位置。

        属性：
        - 时间复杂度取决于散列表的大小和冲突的数量。

        参数：
            hashtable (dict)：待搜索的散列表。
            key：要搜索的目标键。

        返回值：
            object：如果找到目标键，则返回对应的值；如果未找到目标键，则返回None。
        """
        hashed_key = hash(key) % len(hashtable)
        step_size = self._second_hash(key)

        while hashed_key in hashtable:
            if hashtable[hashed_key][0] == key:
                return hashtable[hashed_key][1]

            hashed_key = (hashed_key + step_size) % len(hashtable)

        return None

    def _second_hash(self, key):
        """
        第二个散列函数，用于双重散列中计算探测步长。

        参数：
            key：要散列的键。

        返回值：
            int：计算得到的散列值。
        """
        # TODO: 根据需要实现适当的第二个散列函数
        return hash(key) % 7


# 使用示例
if __name__ == "__main__":
    my_hashtable = {
        0: ("apple", "red"),
        1: ("banana", "yellow"),
        2: ("cherry", "red"),
        3: ("date", "brown"),
        4: ("elderberry", "purple"),
        5: ("fig", "purple"),
        6: ("grape", "green"),
        7: ("honeydew", "green"),
        8: ("kiwi", "brown"),
        9: ("lemon", "yellow")
    }
    target_key = 6

    search_obj = HashTableSearch()

    # 线性搜索
    result = search_obj.linear_search(my_hashtable, target_key)
    # 输出：Linear search result: ('grape', 'green')
    print("Linear search result:", result)

    # 散列搜索
    result = search_obj.hash_search(my_hashtable, target_key)
    # 输出：Hash search result: ('grape', 'green')
    print("Hash search result:", result)

    # 线性探测搜索
    result = search_obj.linear_probing_search(my_hashtable, target_key)
    # 输出：Linear probing search result: ('grape', 'green')
    print("Linear probing search result:", result)

    # 二次探测搜索
    result = search_obj.quadratic_probing_search(my_hashtable, target_key)
    # 输出：Quadratic probing search result: ('grape', 'green')
    print("Quadratic probing search result:", result)

    # 双重散列搜索
    result = search_obj.double_hashing_search(my_hashtable, target_key)
    # 输出：Double hashing search result: ('grape', 'green')
    print("Double hashing search result:", result)
